package com.lhcai.nk;

/**
 * @author lhcstart
 * @create 2023-02-24 22:08
 */

import javax.xml.transform.Source;

/**
 * 最小覆盖子串
 */
public class NC28 {
    public static void main(String[] args) {
        NC28 nc28 = new NC28();
        String s = nc28.minWindow("aa", "aa");
        System.out.println(s);
    }

    /**
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow(String S, String T) {
        // write code here
        int n = S.length();
        int m = T.length();

        //将T中字母出现的次数存入数组
        int[] map1 = new int[128];
        for (int i = 0; i < m; i++) {
            map1[T.charAt(i)]++;
        }

        int len = 10001;
        int start = 0;
        for (int i = 0; i < n; i++) {//遍历S
            //每次得到的子串 ，字母出现的次数 都要重新放入数组
            int[] map2 = new int[128];
            for (int j = i; j < n; j++) {//遍历S 的所有子串
                map2[S.charAt(j)]++;
                if (match(map1, map2) && len > j - i + 1) {
                    len = j - i + 1;
                    start = i;
                }
            }
        }
        return len == 10001 ? "" : S.substring(start, start + len);
    }

    //简单的判断子串是否符合规则
    public boolean match(int[] map1, int[] map2) {
        for (int i = 0; i < 128; i++) {
            if (map1[i] > map2[i]) {
                return false;
            }
        }
        return true;
    }

}
